1. Field of the Invention
This invention relates to computer data storage and server systems, and more particularly to digital video/audio storage and playback systems supporting multiple continuous media streams.
2. Description of the Related Art
Multimedia or video server systems are used in a variety of applications for the storage and playback of video, audio or other multimedia data streams. For example, multimedia servers may be used for broadcast, cable, satellite or telco solutions to distribute multimedia information to clients or consumers. Professional broadcasters and associated service providers, such as networks and affiliates or cable providers, may employ digital video servers to support high bandwidth multimedia broadcast applications including multi-channel program playout, ad insertion, and digital content management. Other applications for multimedia server systems may include computer-based training in which multimedia training materials or lectures may be stored on the server system accessed by students over a network or the internet.
Video archiving, browsing and retrieval is another multimedia server application. Various movies may be stored by the server and distributed to users upon request. Video-on-demand or video delivery systems may enable a plurality of users or viewers to selectively watch movies or other audio/video sequences which are stored on one or more video servers or media servers. The video servers may be connected through data transfer channels, such as a broadcast cable system, satellite broadcast system or the internet, to the plurality of users or subscribers. The video servers may store a plurality of movies or other audio/video sequences, and each user can select one or more movies from the video servers for viewing. Each user may include a television or other viewing device, as well as associated decoding logic, for selecting and viewing desired movies. When a user selects a movie, the selected movie may be transferred on one of the data transfer channels to the viewing device of the respective user. Multimedia servers are also found in webcasting applications in which entertainment may be multicast on the internet to different subscribers. Multimedia servers are found in numerous other applications as well.
To meet the demands of many different applications and users, it is desirable for a multimedia server system to provide flexibility and extensibility. Two important requirements for a multimedia server system are storage space and filesystem bandwidth. Multimedia data, such as full-motion digital video, requires a large amount of storage and data transfer bandwidth. Thus, multimedia systems use various types of video compression algorithms to reduce the amount of necessary storage and data transfer bandwidth. In general, different video compression methods exist for still graphic images and for full-motion video. Video compression methods for still graphic images or single video frames may be intraframe compression methods, and compression methods for motion video may be interframe compression methods.
Examples of video data compression for still graphic images are RLE (Run-Length Encoding) and JPEG (Joint Photographic Experts Group) compression. Although JPEG compression was originally designed for the compression of still images rather than video, JPEG compression is used in some motion video applications. Most video compression algorithms are designed to compress full motion video. Examples of video compression techniques are MPEG (Moving Pictures Experts Group), MPEG-2, DVI (Digital Video Interactive) and Indeo, among others.
Even with the use of compression techniques, multimedia applications may still require extremely large amounts of storage. For example, two hours of video encoded at 1 Mb per second may require roughly one gigabyte (1 GB) of storage. A system supporting numerous different content may require up to several terabytes (TB) of storage. The server system must also be able to provide enough bandwidth for the various users to access selected multimedia content without overloading the storage system. For example, to support 100 simultaneous subscribers viewing multimedia content encoded at 1 Mb per second, a server may need to support a bandwidth in excess 100 Mb per second when allowing for overhead. If enough bandwidth is not available, then some requests may have to be denied, or the play quality may suffer (video may run too slowly or may appear xe2x80x9cjerkyxe2x80x9d). To meet such storage and bandwidth needs, a multimedia server may utilize one or more RAID storage systems. In a RAID system, for a given multimedia file, blocks of multimedia data may be stored across multiple hard disk units. The blocks may be read out or transferred to the communication network and transmitted or broadcast to the user or users. At the receiving end the blocks may be decoded for user viewing on a display device.
The use of hard disk drives to store information magnetically is well known. A single hard disk drive typically includes several rotating disks or platters upon whose surfaces information may be written or read by a read/write head. Within a hard disk drive the platters rotate together and all read/write heads typically are moved simultaneously to access different platter positions. A platter typically is formatted into concentric tracks that define collectively, platter-to-platter, a family of concentric cylinders, and into sectors that represent a portion of a track. A controller associated with the hard disk unit determines which cylinder, read/write head and sector is to be accessed for reading or writing.
The platters may also be considered as being divided into zones. Since they are physically larger, tracks in zones at the outer platter parameter contain more sectors than tracks in zones near the rotational axis of the platter. Therefore, assuming the platters rotate with a constant velocity, the data bandwidth available from the outer most zones is greater than the data bandwidth available from the innermost zones. Even with modem hard disk drives, there can be a 2-1 variation between worst case and average case disk transfer bandwidth due to sectors/track variations between outer and inner zones.
Many multimedia applications require continuous media streams in which data streams must be delivered at a specified and possibly time-varying data rates and with a specified uniformity of that delivery rate. To support continuous media streams, prior video streaming systems have been based on a constant time, variable data storage scheduler. Constant time, variable data schedulers deliver a stream at a particular bit rate by accessing the disk with a frequency that is common with all streams and varying the amount of data fetched at each period to meet the required data rate of the stream. The admission control problem for constant time, variable data disk schedulers is fairly straight forward. A new stream may be admitted if the disk can sustain the required aggregate data rate over the fixed access period. FIG. 1 illustrates a constant time/variable data rate dependent data placement/scheduling mechanism. For simplicity only two streams are illustrated. Data blocks 100 are accessed at a fixed period common to all streams. The size of the data blocks 100 is varied between different streams according to the rate required for a particular stream. As shown in FIG. 1, stream one has a larger block size and thus a higher data rate than stream two. When streams are recorded to disk using a constant/time variable data scheduling mechanism, the placement of data on the disks is rate dependent.
Constant time schedulers may have some deficiencies however. These deficiencies may include significant internal fragmentation of storage. Internal fragments occur because storage is allocated in multiples of some fixed-size block. A minimum block size is the size of the device sector, but typically the blocks may be larger to minimize the size of free block lists. Internal fragmentation may occur in every block file. For example, fifty percent of storage could be lost to internal fragmentation when the desired bit rate just exceeded what was deliverable by a certain block size per period.
Constant time schedulers may also suffer from a loss of bandwidth capability due to internal fragmentation. Internal fragmentation results in a loss of storage bandwidth because the system must fetch unused bytes.
Constant time schedulers may also suffer from significant external fragmentation of storage. Because storage is allocated and freed in variable blocks, storage can be lost for use by high bit-rate files due to external fragmentation. Some constant time systems avoid this problem by aggregating their variable data from multiple discontinuous storage blocks. However, in doing so they lose storage performance by requiring additional seeks.
Another deficiency of constant time schedulers is that they may require a more complicated file system to accommodate variable block sizes. The scan requires decision-making mechanisms to choose between best fit and first fit blocks, and between blocks on a disk""s inner or outer zones, to mention only two complicating factors. Other complicating factors arise when allocating memory buffers to hold the variable-size data blocks.
Constant time schedulers result in bit-rate dependent block allocation of storage. Bit-rate dependence is inherent in constant time schedulers because the block size is chosen based on the desired stream bit rate. Thus, a file""s desired streaming rate must be known prior to writing the stream to storage.
Constant time schedulers also typically lack of support for a pull model and variable bit-rate streaming. In general, because block size and placement are based on a given anticipate stream rate, accommodating variable bit streams and implementing a pull model is impractical.
While most of the above points are implementation or efficiency issues, lack of pull-model support is a functional issue with significant implications. It makes non-real-time migration of video files difficult. It also complicates solutions in cases where other devices are unable to slave to a server""s clock or are forced to slave to another clock source, such as where encoders and decoders in a broadcast environment are slaved to a xe2x80x9cstudio clock.xe2x80x9d Non-real-time migration and providing input and output to externally clocked devices are important requirements for the broadcast environment.
Thus it is desirable to have a multimedia server and storage system that may guarantee performance on an arbitrary mix continuous multimedia streams including reads, writes, varying bit rates, single files, and multiple files. A technique for controlling stream admission is desirable to ensure that current stream rates may be guaranteed. Efficient high utilization of disk bandwidth is also desirable.
A multimedia storage manager may operate by associating a ring of data buffers between the requestor of continuous media and the disk subsystem. The number of buffers in the ring may be a function of a contracted guarantee rate of the associated media stream, configurable parameters of the disk scheduling system, and service characteristics of the disk system.
This ring of N buffers may be used to hold the next N blocks of the continuous media stream to be accessed by the requester. Once a buffer in the ring has its data consumed by the requester, the now empty buffer along with a deadline time is queued with the disk scheduler. The deadline time indicates the latest time when the buffer can be filled and meet the guaranteed rate requirement of the stream. It is calculated simply as currentTime+(Nxe2x88x921)*buftime, where bufTime is the minimum time in which the requestor can consume a buffer without exceeding the contracted rate guarantee.
Simultaneously with guaranteed rate requests being queued with the disk scheduler, prioritized, but non-guaranteed rate requests are also queued. Non-guaranteed rate requests do not carry deadlines, but do carry priorities.
In a preferred embodiment, the disk scheduler issues the queued requests to disk in an order which meets the deadlines associated with the request, obtains a high proportion of the disk system bandwidth, and allocates residual disk bandwidth after guaranteed requests to non-guaranteed requests in a manner consistent with their associated priorities.
The storage manager places requests from continuous media requesters into a earliest deadline ordered queued (the xe2x80x9cdeadline queuexe2x80x9d), and it places prioritized non-guaranteed rate requests into a separate highest priority ordered queue (the xe2x80x9cpriority queuexe2x80x9d).
The disk scheduler may also maintain a third list of disk requests. This list has requests ordered by the position of the requested data block on the disk device. This list is referred to later as the xe2x80x9cseek reorder queuexe2x80x9d. The seek reorder queue may have fixed maximum size that is a configurable parameter of the system. Requests from the two queues described above are migrated to this list.
Requests are migrated from the deadline and priority queues to the seek reorder queue in a xe2x80x9ccyclexe2x80x9d. A cycle is of a fixed number of requests and within the cycle xe2x80x9cslotsxe2x80x9d are assigned to either the deadline queue or the priority queue in proportion equal to the desired allocation of disk bandwidth between guaranteed and non-guaranteed access. The slots allocated to each use are evenly distributed through the cycle.
Requests from the deadline and priority queues are migrated to the seek reorder queue whenever the seek reorder queue is not filled to its maximum size. Each migration is done from the queue indicated by the current slot of the cycle and then the cycle advances to the next slot. If the queue indicated by the slot is empty, then an entry from the alternate queue is chosen if it is non-empty. The migrated entry is ordered in the seek reorder queue such that all requests to one side of it refer to data blocks with disk addresses greater than or equal to its and all blocks on the other side in the list have data blocks with disk address less than or equal to its.
The seek reorder queue is concurrently traversed by a thread that moves continuously in one direction (i.e. in increasing or decreasing disk addresses) until no further entries exist on the list, it then reverses direction and resumes. This thread at each step issues the disk request to the disk subsystem and advances to the next request when the previously issued request has been completed by the disk system.
In a preferred embodiment, the storage manager ensures that bandwidth is allocated as desired between guaranteed and non-guaranteed rate requestors, allows for prioritized non-guaranteed access, and reduces average seek distance as disk load increases.
The system also addresses admission control (e.g. determining if an additional guaranteed rate requestor can be accommodated without impacting service to existing guaranteed rate requestors) and determination of the appropriate number of buffers in a ring for a desired guaranteed stream access rate.
Admission control may be addressed by characterizing the disk system performance with a synthetic load that reflects the characteristics of a typical load. Construction of a representative load may be simplified by constraining the file system to allocate sequential blocks in a xe2x80x9czoned randomxe2x80x9d manner: the disk block address range is divided into two halves, sequential file block allocations are chosen from random positions within a zone and then alternating between the two zones. In a preferred embodiment, this process is followed because disk systems have performance variations with respect to block address. Allocating from alternate xe2x80x9czonesxe2x80x9d ensures that disk performance is approximately equal both across different files and across positions within a single file. The synthetic load is now a single zoned allocation sequence which is sufficiently representative of the true load (and aggregation of multiple of zoned allocations). Disk performance may be characterized with this load and derated to provide margin. The derated bandwidth value may then be multiplied by the fraction of total bandwidth allocated in the xe2x80x9ccyclexe2x80x9d process to guaranteed rate requestors. This results in the maximum admission bandwidth. Guaranteed rate requestors may now be admitted until they have consumed the entire admission bandwidth.
Determination of the appropriate number of buffers in the buffer ring may be done empirically. This may be done by running a collection of guaranteed rate streams, all contracted for the same rate. The rate is chosen so that the collection of streams exactly consumes the entire admission bandwidth. All streams are initiated against the scheduler simultaneously. Ring buffers are then sized to assure that all deadlines are met with a stated margin. The margin may be a configurable parameter.
Generally speaking, one embodiment includes a system for scheduling storage accesses of multiple continuous media streams. The system may include a plurality of media stream clients. Associated with each media stream client is one of a plurality of media stream managers. Each media stream manager maintains a ring of buffers configured to buffer media stream data between its associated media stream client and one or more storage systems. A different deadline queue may be associated with each one of the storage systems. Each deadline queue may be configured to queue buffer requests from the media stream managers. Each buffer request may include a deadline by which the buffer request must be fulfilled by the corresponding storage system. Each media stream manager may be configured so that once one of its buffers is consumed by the associated media stream client, the media stream manager submits a buffer request and deadline for that buffer to the appropriate deadline queue. Buffer requests may be ordered in each deadline queue from earliest to latest deadline. Each media stream manager may be configured to provide a guaranteed maximum media stream rate to its associated media stream client. The system may also include an admission controller configured to negotiate a maximum media stream rate with each media stream client. The admission controller may allow additional media stream clients only if negotiated maximum media stream rates can be maintained for all current media stream clients.
For each ring of buffers, each buffer is consumed by its associated media stream client one after another in a circular order. Each buffer may be equally sized to hold one block of data, where data is accessed in the storage systems according to a block. Each ring of buffers may contain a number of buffers, where the number is chosen according to a maximum stream rate requested by the associated media stream client. The number is chosen to provide just enough buffers to avoid underrun at the maximum stream rate. The system may also include a bandwidth allocator configured to allocate a set portion of storage system bandwidth to request from the deadline queue for a storage system and the remaining storage system bandwidth to non-rate-guaranteed requests.
One embodiment may include a method for scheduling storage accesses of multiple continuous media streams. The method may include establishing a guaranteed maximum stream rate for each of a plurality of multimedia streams. The method may further include establishing a ring of buffers for each multimedia stream with each multimedia stream fulfilling multimedia data requests from its associated ring of buffers. As each buffer in one of the ring of buffers is consumes, the method includes queuing a request for that buffer in a deadline queue associated with the storage system from which the request is to be satisfied. For each deadline queue the method includes issuing requests from the deadline queue to the associated storage system. The request with the earliest deadline is issued first. Queuing the request may include calculating a deadline time indicating the latest time by which the buffer request can be fulfilled and still meet the corresponding guaranteed maximum stream rate.
An embodiment may include a method for managing a multimedia data stream. The method may include receiving a request from a stream requester to establish a multimedia data stream to access a multimedia file stored on a storage system. The method may include linking to the multimedia file and creating a ring of buffers. The method may further include initially filling the ring of buffers with multimedia data for the stream and then streaming multimedia data between the multimedia file on the storage system and the multimedia stream requester. Streaming multimedia data may include consuming one of the buffers in the ring of buffers and then generating a request and a deadline for the just consumed buffer. The deadline may indicate the latest time the request must be fulfilled in order to prevent buffer underrun. The streaming then includes issuing the request and deadline for the just consumed buffer to a deadline queue. The request may be ordered in the deadline queue according to the deadline. The next buffer in the ring of buffers may then be consumed and the process repeated.
A system for managing storage accesses for rate guaranteed continuous multimedia data streams and non-rate-guaranteed storage requests may include a plurality of rate guaranteed requestors for multimedia streams and one or more non-rate guaranteed requestors. A disk scheduler may also be included. The disk scheduler may have a guaranteed rate queue for queuing storage requests from the rate guaranteed requestors and a non-rate-guaranteed queue for queuing requests from the non-rate-guaranteed requesters. The disk scheduler may also include a bandwidth allocator coupled to the guaranteed rate queue and the non-rate-guaranteed queue and further coupled to a storage system. The bandwidth allocator may be configured to allocate bandwidth of the storage system between the guaranteed rate queue and the non-rate-guaranteed queue according to a predetermined ratio. The rate guaranteed requesters may be limited so that an aggregate of maximum stream rates guaranteed for each rate guaranteed requestor does not exceed the portion of the bandwidth allocated to the guaranteed rate queue.
Requests may be ordered in the guaranteed rate queue according to a deadline where the deadline for each request indicates a latest time by which that request must be fulfilled to meet a guaranteed maximum stream rate for the corresponding multimedia data stream. Requests may be ordered in the non-rate guaranteed queue according to a priority where the bandwidth allocator is configured to migrate the request with the highest priority from the non-rate-guaranteed queue. The system may also include a buffer ring for each multimedia data stream from one of the rate guaranteed requestors. The buffer ring may buffer multimedia stream data between an associated rate guaranteed requestors and the disk scheduler. The buffer ring may contain a number of buffers chosen to prevent buffer underrun at a guaranteed maximum stream rate. The buffers of each buffer ring may be consumed by the associated rate guaranteed requestor one after another in a circular order. As each buffer is consumed a request and a deadline for the just consumed buffer may be issued to the guaranteed rate queue.
A method for managing storage accesses for rate guaranteed continuous multimedia data streams and non-rate-guaranteed storage requests may include allocating a portion of the storage systems bandwidth to stream requests from rate guaranteed requestors and allocating the remaining portion of the storage systems bandwidth to request from non-rate-guaranteed requestors. Storage requests from rate guaranteed requestors may be queued in a guaranteed rate queue and storage requests from non-guaranteed rate requestors may be queued in a non-rate guaranteed queue. The method further includes selecting either the guaranteed rate queue or the non-rate-guaranteed queue according to the bandwidth allocation in order to migrate one of the requests to the storage system. Each guaranteed rate requestor may request access for a multimedia stream having a maximum guaranteed rate. The method includes limiting the number of multimedia streams so that the aggregate of the maximum guaranteed rate for each stream does not exceed the bandwidth allocated to stream requests from rate guaranteed requestors. Unused bandwidth for guaranteed rate requests may be dynamically reallocated to non-rate-guaranteed requests and vice versa.
A system and method may be provided for configuring or tuning a media storage system. The method may include characterizing a maximum sustainable throughput for the media storage system. The maximum sustainable throughput may be decreased by a primary derate parameter to obtain a primary throughput. The method may further include determining sizes for buffer units at different media stream rates where during operation each buffer unit is used for buffering a media data stream between a media stream requestor and the storage system. The buffer unit sizes may be determined by generating stream simulators sufficient to consume the primary throughput and then optimizing the buffer sizes to prevent underruns for the stream simulators. This may be repeated at different stream rates in order to determine a table of buffer sizes versus stream rates. The method may also include decreasing the primary throughput to obtain a maximum system bandwidth which, during operation of the system, sets an upper limit on admission of streams. The amount by which the primary throughput is decreased for this purpose may be determined by a configurable secondary derate parameter.
When buffer sizes are determined, a prefill margin parameter may be set by which request deadlines must be met. Also, an available rate parameter may be set to proportion available bandwidth between rate guaranteed streams and non-rate guaranteed requests. The proportion allocated for rate guaranteed requests may be used to determine buffer sizes that are able to meet the configured prefill margin. Another parameter may be configured to set the length of a seek reorder queue that orders storage system requests according to their physical storage address. This parameter allows a tradeoff between seek efficiency and variability in service time. A higher variability in service time may require larger buffer ring sizes. Also, the block size by which data is accessed in the storage system may be configured.